/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution279 {

    public static void main(String args[]){
        Solution279 s = new Solution279();
        System.out.println(s.numSquares(2000000));
    }

    int minv = Integer.MAX_VALUE;
    public int numSquares(int n) {
        dfs(n, 1, 0);
        return minv;
    }

    public void dfs(int sum, int st, int count){
        if(count > minv){
            return;
        }
        if(sum == 0){
            minv = minv > count ? count : minv;
            return;
        }
        int v = st * st;
        if(v > sum){
            return;
        }
        for(int i = 0 ; i * v <= sum; i ++){
            dfs(sum - i * v, st + 1, count + i);
        }
    }
}
